package com.wdc.recursion;

import java.util.Arrays;

@SuppressWarnings({"all"})
public class E01Fibonacci {
    public static void main(String[] args) {
        System.out.println("llll");
//        System.out.println(f(9));
    }

    /**
     * 斐波那契数列
     * @param n 要求的第几项数
     * @return
     */
    /*
        求斐波那契数列的调用次数:     2*f(n+1) - 1
     */
    public static int f(int n,int[] cache){

       /* if (n == 0){
            return n;
        }
        if (n == 1){
            return n;
        }*/

        if (cache[n] != -1){
            return cache[n];
        }

        int x = f(n - 1,cache);
        int y = f(n - 2,cache);
        cache[n] = x + y;


        return cache[n];


    }

    /**
     * 使用Memoization (记忆法，备忘录) 改进
     */
    public static int fibonacci(int n){
        int[] cache = new int[n + 1];
        Arrays.fill(cache,-1);
        return f(n,cache);
    }

}
